package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.LinkedList;

/**
 * 这简单题怎么这么费劲
 * <p>
 * 这道题做错了，很好
 * 找到了自己思维漏洞，针不戳
 */
public class _1047_remove_adjacent_duplicate_char {
    
    /**
     * 我就是不想好好做！
     * <p>
     * 我尼玛！超出时间限制！
     */
    public String removeDuplicates1(String s) {
        while (true) {
            String ns = s.replaceAll("(\\w)\\1", "");
            if (s.equals(ns))
                return s;
            s = ns;
        }
    }
    
    /**
     * 当我想好好做时
     * 发现没思路
     * <p>
     * 说出你的想法！
     * 不停地循环，消除，往慢索引那放，然后，下一轮，最后，返回 slow end
     * 之间的字符串！
     * <p>
     * abbaca
     * ca
     * <p>
     * 很好……改了半个小时改了一版
     * <p>
     * 又超时！
     * 操你妈！
     */
    public String removeDuplicates2(String s) {
        char[] arr = s.toCharArray();
        boolean repeat = true;
        int end = arr.length;
        while (repeat) {
            repeat = false;
            // 两两消除
            int i = 0, j = 0;
            while (j < end) {
                while (j < end - 1 && arr[j] == arr[j + 1]) {
                    repeat = true;
                    j += 2;
                }
                if (j >= end) break;
                arr[i++] = arr[j++];
            }
            end = i;
        }
        return new String(arr, 0, end);
    }
    
    /**
     * 既然是栈和队列，那估计是队列！我试试！
     * <p>
     * 过了反正，效率是不高
     */
    public String removeDuplicates3(String s) {
        LinkedList<Character> q = new LinkedList<>();
        while (true) {
            boolean change = false;
            for (int i = 0; i < s.length(); i++) {
                if (!q.isEmpty() && q.peekLast() == s.charAt(i)) {
                    change = true;
                    q.pollLast();
                } else
                    q.offer(s.charAt(i));
            }
            StringBuilder ss = new StringBuilder();
            q.forEach(ss::append);
            s = ss.toString();
            q.clear();
            if (!change) break;
        }
        return s;
    }
    
    /**
     * 改改我自己的
     * 还可以抢救
     * <p>
     * 必须用队列，不然顺序就错了
     * 又错一次！
     */
    public String removeDuplicates31(String s) {
        LinkedList<Character> q = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (!q.isEmpty() && q.peekLast() == s.charAt(i)) q.pollLast();
            else q.offer(s.charAt(i));
        }
        StringBuilder ss = new StringBuilder();
        q.forEach(ss::append);
        return ss.toString();
    }
    
    /**
     * ...
     * <p>
     * 操！
     * 看来我这里有思维漏洞！
     */
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
    
}
